public class MySort {
    // 插入排序
public static void insertSort(int[] array){
        // write code  here
    for (int i = 1; i < array.length; i++) {
        int tmp = array[i] ;
        int j = i-1 ;
        for (; j >= 0 ; j--) {
            if(array[j] > tmp){
                array[j+1] = array[j] ;
            }else {
                break ;
            }
        }
        array[j+1] = tmp ;
    }
    }

        // 希尔排序
        public static void shellSort(int[] array){
        // write code  here
            int gap = array.length;
            while(gap > 1){
                gap /= 2 ;
                shell(array , gap);
            }
       }
       private static void shell(int[] array , int gap){

           for (int i = gap; i < array.length; i++) {
               int tmp = array[i] ;
               int j = i-gap ;
               for (; j >= 0 ; j-=gap) {
                   if(array[j] > tmp){
                       array[j+gap] = array[j];
                   }else{
                       break;
                   }
               }
               array[j+gap] = tmp ;
           }
       }
    private static void swap(int[] array , int x, int y){
      int tmp = array[x];
      array[x] = array[y];
      array[y] = tmp;

    }
    // 选择排序
public static void selectSort(int[] array){

    for (int i = 0; i < array.length; i++) {
        int minIndex = i ;
        for (int j = i+1; j < array.length ; j++) {
            if(array[j] < array[minIndex]){
                minIndex = j ;
            }
        }
        swap(array , minIndex , i);
    }
        // write code  here
    }


    // 堆排序
   public static void heapSort(int[] array){
        // write code  here
         createHeap(array);
         int len = array.length -1;
         while (len > 0){
             swap(array , 0 , len);
             shiftDown(array , 0 , len);
             len -- ;
         }

    }
    private static void createHeap(int[] array){
        int parent = (array.length-1-1) / 2 ;
        while (parent >= 0){
            shiftDown(array , parent , array.length);
            parent -- ;
        }
    }
    private static void shiftDown(int[] array , int parent , int len){
     int child = parent*2 +1  ;
     while(child < len){
         if(child+1 < len && array[child+1] > array[child]){
             child ++ ;
         }
         if(array[parent] < array[child]){
             swap(array , parent , child);
         }
         parent = child ;
         child = parent*2 +1;
     }
    }

    // 冒泡排序
public static void bubbleSort(int[] array){
        // write code  here

    for (int i = 1; i < array.length; i++) {
        for (int j = 0; j < array.length-i; j++) {
            if(array[j] > array[j+1]){
                swap(array,j ,j+1);
            }
        }

    }


    }

// 快速
   public static void quickSort(int[] array){
        // write code  here
       quick(array , 0 , array.length-1);
    }
    private static void quick(int[] array , int left , int right){
       if(left >= right) return;
       //三数区中
        int index = minOfThree(array , left , right);
        swap(array , left , index);

       int pivot = partition(array , left , right) ;
       quick(array , left , pivot-1);
       quick(array , pivot+1 , right);
    }
    private static int partition(int[] array , int left , int right){
        int key = array[left] ;
        int tmp = left ;
         while(left < right){
              while(left<right && array[right] >= key){
                  right -- ;
              }
              while (left<right && array[left] <= key){
                  left ++ ;
              }
          swap(array , left , right);
         }
        swap(array , tmp, left );
        return  left;
    }
    private static int minOfThree(int[] array , int left , int right){
          int mid = (right-left)/2 ;
          if(array[left] < array[right]){
             if(array[mid] < array[left]){
                 return left;
             }else if(array[mid] > array[right]){
                 return right ;
             }else{
                 return mid ;
             }
          }else {
              if(array[mid] < array[right] ){
                  return right;
              } else if (array[mid] > array[left]) {
                  return left;
              }else {
                  return mid;
              }
          }
    }

}
